/**
 * @file   star_tree.hpp
 * @author wolfhead <wolfhead@wolfhead-laptop>
 * @date   Thu Dec 29 13:55:37 2011
 * 
 * @brief  
 * 
 * 
 */
#ifndef ACAPELLA_STAR_TREE_HPP
#define ACAPELLA_STAR_TREE_HPP

#include <map>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#include <iostream>
#include "traits/type_traits.hpp"
#include "shared_ptr.hpp"
#include "string/string_util.hpp"

namespace acapella
{


template<
    typename FieldType,
    typename KeyType,
    typename ValueType
    >
class StarTree;



template<typename ValueType>
class NodeOperation
{
public:

    static bool Compare(const ValueType& lho, const ValueType& rho);

    template<typename IteratorType>
    static ValueType Average(const IteratorType& itBegin, const IteratorType& itEnd);

    template<typename IteratorType>
    static ValueType Aggregate(const IteratorType& itBegin, const IteratorType& itEnd);
};


class StarTreeError
{
public:
    enum
    {
        SUCCESS = 0,
        ERROR_NODE_NOT_EXIST,
        ERROR_CREATE_NODE_FAIL,
        ERROR_INVALID_PARAM,
        ERROR_ADD_NON_LEAF_NODE,
        ERROR_UPDATE_NODE_FAIL,
        ERROR_DELETE_ROOT,
        ERROR_DELETE_FAIL,
        ERROR_NO_STAR_NODE
    };

    static const char * GetErrorMessage(int code)
    {
        static const char * error [] = {
            "SUCCESS - success",
            "ERROR_NODE_NOT_EXIST - the node under the given param do not exist",
            "ERROR_CREATE_NODE_FAIL - node creation fail (internal)",
            "ERROR_INVALID_PARAM - the param do not match the field list",
            "ERROR_ADD_NON_LEAF_NODE - try to add a non-leaf node to the tree",
            "ERROR_UPDATE_NODE_FAIL - cascading update node fail",
            "ERROR_DELETE_ROOT - delete root node is not permitted",
            "ERROR_DELETE_FAIL - delete node fail (internal)",
            "ERROR_NO_STAR_NODE - no star node found at a non-leaf node"
        };

        if (code < 0 || code > (int)(sizeof(error) / sizeof(const char *)))
        {
            return "unknown error";
        }
        else
        {
            return error[code];
        }
    }
};

//////////////////////////////////////////////////////////////////////
// StarTree
 
template<
    typename FieldType,
    typename KeyType,
    typename ValueType
    >
class StarTree
{
public:
    enum
    {
        STAR_KEY = 0,
        EMPTY_KEY = 1
    };

    class TreeNode;
    typedef TreeNode * TreeNodePtr;

    class iterator;

    typedef StarTree self;
    typedef unsigned short KeyId; 
    typedef std::map<KeyType, KeyId> KeyNameMap;
    typedef std::map<KeyId, KeyType> KeyIdMap;

    typedef std::vector<KeyNameMap> KeyNameMapList;
    typedef std::vector<KeyIdMap> KeyIdMapList;
    typedef std::vector<FieldType> FieldListType;
    typedef std::map<FieldType, KeyType> ParamType;

public:
    StarTree(
        const FieldListType& fieldList,
        const KeyType& starKey,
        const KeyType& emptyKey,
        const KeyType& emptyKeyValue)
        : fieldList_(fieldList)
        , starKey_(starKey)
        , emptyKey_(emptyKey)
        , emptyKeyValue_(emptyKeyValue)
    {
        pRoot_ = new TreeNode(0, NULL);
        Initialize();
    }

    ~StarTree()
    {
        delete pRoot_;
    }

    int Add(
        const ParamType& param, 
        const ValueType& value
        )
    {
        size_t depth = fieldList_.size();

        TreeNodePtr pCurrentNode = pRoot_;
        
        // find the leaf node
        for (size_t currentDepth = 0; currentDepth != depth; ++currentDepth)
        {
            typename ParamType::const_iterator keyIt 
                = param.find(fieldList_[currentDepth]);

            // if this level's key has been found
            // set it to be the current
            if (keyIt != param.end())
            {
                KeyId keyId = CreateKeyMap(currentDepth, keyIt->second);

                TreeNodePtr pNode = pCurrentNode->CreateNode(keyId);
                if (!pNode)
                {
                    return StarTreeError::ERROR_CREATE_NODE_FAIL;
                }

                pCurrentNode = pNode;
            }
            else
            {
                return StarTreeError::ERROR_INVALID_PARAM;
            }
        }

        if (!pCurrentNode->IsLeaf())
        {
            return StarTreeError::ERROR_ADD_NON_LEAF_NODE;
        }

        // set the node's value
        // if the value is modified
        // add it parent node to the uodate list
        pCurrentNode->SetValue(value);

        return StarTreeError::SUCCESS;
    }
    

    TreeNodePtr Get(const ParamType& param)
    {
        size_t depth = std::min<size_t>(param.size(), fieldList_.size());

        TreeNodePtr pCurrentNode = pRoot_;
        TreeNodePtr pNode = NULL;
        KeyId keyId = STAR_KEY;
        
        // for each level in the param
        for (size_t currentDepth = 0; currentDepth != depth; ++currentDepth)
        {
            typename ParamType::const_iterator keyIt 
                = param.find(fieldList_[currentDepth]);

            // if this level's key has been found
            if (keyIt != param.end())
            {
                keyId = GetKeyId(currentDepth, keyIt->second);
                pNode = pCurrentNode->GetNodeByKey(keyId);
            }
            else
            {
                break;
            }

            if (!pNode)
            {
                return NULL;
            }
            else
            {
                pCurrentNode = pNode;
            }
        }

        return pCurrentNode;
    }

    int Delete(const ParamType& param)
    {
        TreeNodePtr pNode = Get(param);
        if (!pNode)
        {
            return StarTreeError::ERROR_NODE_NOT_EXIST;
        }

        TreeNodePtr pParent = pNode->GetParent();
        if (!pParent)
        {
            // delete root is not permitted
            return StarTreeError::ERROR_DELETE_ROOT;
        }

        if (0 != pParent->DeleteNode(pNode->GetKeyId()))
        {
            return StarTreeError::ERROR_DELETE_FAIL;
        }

        return 0;
    }

    int Update()
    {
        pRoot_->Update();

        return StarTreeError::SUCCESS;
    }

    int MergeLimit(const ValueType& limit)
    {
        pRoot_->MergeLimit(limit);

        Update();

        return StarTreeError::SUCCESS;
    }

    const KeyType& GetKey(size_t depth, KeyId id)
    {
        return GetKeyName(depth, id);
    }


    void DumpFieldInfo(std::ostream& os = std::cout)
    {
        for (typename FieldListType::iterator it = fieldList_.begin();
             it != fieldList_.end();
             ++it)
        {
            os << it - fieldList_.begin() << ".\t" << *it << std::endl;
        }
    }

    void DumpKeyInfo(std::ostream& os = std::cout)
    {
        for (size_t depth = 0; depth != fieldList_.size(); ++depth)
        {
            os << "############### " << fieldList_[depth] << " #################" << std::endl;
            for (typename KeyIdMap::const_iterator it = keyIdList_[depth].begin();
                 it != keyIdList_[depth].end();
                 ++it)
            {
                os << it->first << ":" << it->second << "\t";
            }
            os << std::endl;
        }
    }

    void DumpTree(std::ostream& os = std::cout)
    {
        return DumpTree(pRoot_, os);
    }

    void DumpTree(TreeNodePtr pNode, std::ostream& os = std::cout)
    {
        for (iterator it(pNode); it != end(); ++it)
        {
            os << acapella::StringUtil::Implode(it->GetParam(*this), "\t")
               << "\t"
               << it->GetValue()
               << std::endl;
        }
    }

    iterator begin()
    {
        return iterator(pRoot_);
    }

    iterator end()
    {
        return iterator();
    }

private:

    int Initialize()
    {
        keyNameList_.resize(fieldList_.size());
        keyIdList_.resize(fieldList_.size());

        for (size_t depth = 0; depth != fieldList_.size(); ++depth)
        {
            KeyId starId = CreateKeyMap(depth, starKey_);
            assert(starId == STAR_KEY && "star should be zero");

            KeyId emptyId = CreateKeyMap(depth, emptyKey_);
            assert(emptyId == EMPTY_KEY && "null should be one");
        }

        return StarTreeError::SUCCESS;
    }

    KeyId CreateKeyMap(size_t depth, const KeyType& key)
    {
        KeyId keyId = STAR_KEY;

        typename KeyNameMap::iterator it = keyNameList_[depth].find(key);
        if (it == keyNameList_[depth].end())
        {
            keyId = keyNameList_[depth].size();
            keyNameList_[depth][key] = keyId;
            keyIdList_[depth][keyId] = key;
        }
        else
        {
            keyId = it->second;
        }

        return keyId;
    }

    KeyId GetKeyId(size_t depth, const KeyType& key)
    {
        typename KeyNameMap::const_iterator it = keyNameList_[depth].find(key);
        if (it != keyNameList_[depth].end())
        {
            return it->second;
        }
        else
        {
            if (key == emptyKeyValue_)
            {
                return EMPTY_KEY;
            }
            else
            {
                return STAR_KEY;
            }
        }
    }

    const KeyType& GetKeyName(size_t depth, KeyId keyId)
    {
        typename KeyIdMap::const_iterator it = keyIdList_[depth].find(keyId);
        assert(it != keyIdList_[depth].end());
 
        return it->second;
    }
    
    TreeNodePtr pRoot_;

    FieldListType fieldList_;

    KeyNameMapList keyNameList_;

    KeyIdMapList keyIdList_;

    KeyType starKey_;

    KeyType emptyKey_;

    KeyType emptyKeyValue_;
};

//////////////////////////////////////////////////////////////////////
// StarTree<FieldType, KeyType, ValueType>::iterator
template<
    typename FieldType,
    typename KeyType,
    typename ValueType
    >
class StarTree<FieldType, KeyType, ValueType>::iterator
{
public:
    iterator()
        : pNode_(NULL)
    {
    };

    iterator(TreeNodePtr pNode)
        : pNode_(pNode)
    {     
        // if the root node is given, move to his first child
        // or if the root is leaf, the set this iterator to be end
        if (pNode && !pNode->GetParent())
        {
            if (pNode->IsLeaf())
            {
                pNode_ = NULL;
            }
            else
            {
                pos_.push(0);
                pNode_ = pNode->GetNodeByIndex(0);
            }
        }
    }

    iterator(const iterator& it)
        : pNode_(it.pNode_)
        , pos_(it.pos_)
    {
    }

    bool operator == (const iterator& it)
    {
        return pNode_ == it.pNode_;
    }

    bool operator != (const iterator& it)
    {
        return !(*this == it);
    }

    const TreeNode& operator*()
    {
        return *pNode_;
    }

    TreeNodePtr operator->()
    {
        return pNode_;
    }

    iterator& operator++()
    {
        Advance();
        return *this;
    }

    iterator& operator++(int)
    {
        iterator old = *this;
        Advance();
        return old;
    }

private:
        
    void Advance()
    {
        // if this is end, return
        if (!pNode_)
        {
            return;
        }

        // if current iterator is not leaf, step into its's child
        if (!pNode_->IsLeaf())
        {
            pos_.push(0);
            pNode_ = pNode_->GetNodeByIndex(0);
            return;
        }

        // try to get it's sibling, or going up
        for (;;)
        {
            if (pos_.empty())
            {
                pNode_ = NULL;
                return;
            }

            size_t index = pos_.top();
            pos_.pop();
            pNode_ = pNode_->GetParent();
            if (!pNode_)
            {
                pNode_ = NULL;
                return;
            }

            if (pNode_->Size() != index + 1)
            {
                ++index;
                pNode_ = pNode_->GetNodeByIndex(index);
                pos_.push(index);
                break;
            }
            else
            {
                continue;
            }
        }
    }

    TreeNodePtr pNode_;
    std::stack<size_t> pos_;
}; 


//////////////////////////////////////////////////////////////////////
// StarTree<FieldType, KeyType, ValueType>::TreeNode

template<
    typename FieldType,
    typename KeyType,
    typename ValueType>
class StarTree<FieldType, KeyType, ValueType>::TreeNode
{
private:

    // node comparsion functor
    class CompareFunctor
    {
    public:
        CompareFunctor(TreeNodePtr pNode)
            : pNode_(pNode)
        {
        }

        bool operator() (KeyId lho, KeyId rho)
        {
            return NodeOperation<ValueType>::Compare(
                pNode_->GetNodeByKey(lho)->GetValue(),
                pNode_->GetNodeByKey(rho)->GetValue()
                );
        }

    private:
        TreeNodePtr pNode_;
    };


    typedef std::map<KeyId, TreeNodePtr> NodeMap;
    typedef std::vector<KeyId> SortList;

public:
    friend class StarTree<FieldType, KeyType, ValueType>;

    class iterator;

    TreeNode(
        KeyId keyId,
        TreeNodePtr pParent)
        : keyId_(keyId)
        , pParent_(pParent)
    {
    }

    ~TreeNode()
    {
        for (typename NodeMap::iterator it = nodeMap_.begin();
                it != nodeMap_.end();
                ++it)
        {
            delete it->second;
        }
    }

    KeyId GetKeyId()
    {
        return keyId_;
    }

    std::vector<KeyType> GetParam(StarTree& tree)
    {
        std::vector<KeyType> param;
        size_t depth = GetDepth() + 1;
        param.resize(depth);
        
        TreeNodePtr pNode = this;
        while (pNode && depth)
        {
            param[depth - 1] = tree.GetKey(pNode->GetDepth(), pNode->GetKeyId());
            pNode = pNode->GetParent();
            --depth;
        }
        return param;
    }
        
    bool IsRoot()
    {
        return NULL == pParent_;
    }

    bool IsLeaf()
    {
        return nodeMap_.size() == 0;
    }

    bool IsChildOf(TreeNodePtr pNode)
    {
        TreeNodePtr pParent = GetParent();
        for (;;)
        {
            if (pParent == pNode)
            {
                return true;
            }
            if (!pParent)
            {
                return false;
            }
        }
    }

    size_t Size()
    {
        return sortList_.size();
    }

    size_t GetDepth()
    {
        size_t depth = 0;
        TreeNodePtr pNode = this;
        while ((pNode = pNode->GetParent()))
        {
            ++depth;
        }
        return depth == 0 ? 0 : depth - 1;
    }

    TreeNodePtr GetNodeByIndex(size_t index)
    {
        if (index < Size())
        {
            return GetNodeByKey(sortList_[index]);
        }

        return NULL;
    }

    TreeNodePtr GetNodeByKey(KeyId keyId)
    {
        typename NodeMap::const_iterator it = nodeMap_.find(keyId);

        if (it == nodeMap_.end())
        {
            it = nodeMap_.find(STAR_KEY);
        }

        if (it == nodeMap_.end())
        {
            return NULL;
        }

        return it->second;
    }


    TreeNodePtr CreateNode(
        KeyId keyId
        )
    {
        typename NodeMap::iterator it = nodeMap_.find(keyId);
        if (it != nodeMap_.end())
        {
            return it->second;
        }
        else
        {
            TreeNodePtr pNode = new TreeNode(keyId, this);
            nodeMap_[keyId] = pNode;
            sortList_.push_back(keyId);
            return pNode;
        }
    }

    int DeleteNode(KeyId keyId)
    {
        TreeNodePtr pNode = GetNodeByKey(keyId);

        if (!pNode)
        {
            return -1;
        }
        
        for (;;)
        {
            // remove the deleted node front the sortList
            SortList::iterator it = std::find(sortList_.begin(), sortList_.end(), keyId);
            if (it == sortList_.end())
            {
                return 0;
            }
            else
            {
                sortList_.erase(it);
            }
        }
        
        nodeMap_.erase(keyId);
        delete pNode;
    }

    int SetValue(const ValueType& value)
    {
        value_ = value;
        return 0;
    }

    TreeNodePtr GetParent()
    {
        return pParent_;
    }

    const ValueType & GetValue()
    {
        return value_;
    }

    int Update()
    {
        if (IsLeaf())
        {
            return 0;
        }

        for (size_t i = 0; i != Size(); ++i)
        {
            GetNodeByIndex(i)->Update();
        }

        // compute the average value of all child into star-node
        _Average();
        // aggregate child-node's value into this node
        _Aggregate();
        // sort child node
        _Sort();

        sortList_.reserve(sortList_.size());

        return 0;
    }

    int Merge(TreeNodePtr pNode)
    {
        std::vector<ValueType> v;
        v.push_back(this->GetValue());
        v.push_back(pNode->GetValue());
        this->SetValue(NodeOperation<ValueType>::Aggregate(v.begin(), v.end()));

        for (size_t i = 0; i != pNode->Size(); ++i)
        {
            TreeNodePtr pNodeToMerge = NULL;
            TreeNodePtr pNodeBeenMerge = pNode->GetNodeByIndex(i);
            if (nodeMap_.find(pNodeBeenMerge->GetKeyId()) == nodeMap_.end())
            {
                pNodeToMerge = CreateNode(pNodeBeenMerge->GetKeyId());
            }
            else
            {
                pNodeToMerge = nodeMap_[pNodeBeenMerge->GetKeyId()];
            }

            pNodeToMerge->Merge(pNodeBeenMerge);
        }

        return 0;
    }

    int MergeLimit(const ValueType& limit)
    {
        std::vector<TreeNodePtr> nodes;

        // merge all node under limit into star-node
        for (size_t i = 0; i != Size(); ++i)
        {
            if (NodeOperation<ValueType>::Compare(limit, GetNodeByIndex(i)->GetValue()))
            {
                if (GetNodeByIndex(i)->GetKeyId() == STAR_KEY)
                {
                    continue;
                }
                nodes.push_back(GetNodeByIndex(i));
            }
        }

        // merge into star and delete the original node
        for (size_t i = 0; i != nodes.size(); ++i)
        {
            TreeNodePtr pStar = CreateNode(STAR_KEY);
            pStar->Merge(nodes[i]);
            DeleteNode(nodes[i]->GetKeyId());
        }

        // if star is under limit delete star
        TreeNodePtr pStar = GetNodeByKey(STAR_KEY);
        if (pStar && NodeOperation<ValueType>::Compare(limit, pStar->GetValue()))
        {
            DeleteNode(STAR_KEY);
        }

        for (size_t i = 0; i != Size(); ++i)
        {
            GetNodeByIndex(i)->MergeLimit(limit);
        }

        return 0;
    }

    iterator begin(size_t index = 0)
    {
        return iterator(this, index);
    }

    iterator end()
    {
        return iterator();
    }

private:

    TreeNodePtr _GetSpecifiedNodeByKey(KeyId keyId)
    {
        typename NodeMap::iterator it = nodeMap_.find(keyId);
        if (it == nodeMap_.end())
        {
            return NULL;
        }

        return it->second;
    }

    int _Sort()
    {
        std::sort(sortList_.begin(), sortList_.end(), CompareFunctor(this));
        return StarTreeError::SUCCESS;
    }

    int _Aggregate()
    {
        SetValue(NodeOperation<ValueType>::Aggregate(begin(), end()));
        return StarTreeError::SUCCESS;
    }

    int _Average()
    {
        TreeNodePtr pNode = _GetSpecifiedNodeByKey(STAR_KEY);
        if (!pNode)
        {
            return StarTreeError::SUCCESS;
        }
        if (pNode->IsLeaf())
        {
            pNode->SetValue(NodeOperation<ValueType>::Average(begin(), end()));
        }
        return StarTreeError::SUCCESS;
    }

    KeyId keyId_;

    SortList sortList_;
    NodeMap nodeMap_;

    ValueType value_;
    TreeNodePtr pParent_;
};

template<
    typename FieldType,
    typename KeyType,
    typename ValueType
    >
class StarTree<FieldType, KeyType, ValueType>::TreeNode::iterator
{
public:
    iterator()
        : pNode_(NULL)
        , pos_(-1)
    {
    }

    iterator(TreeNodePtr pNode, int pos)
        : pNode_(pNode)
        , pos_(pos)
    {
        if (!pNode_ || (int)pNode_->Size() <= pos_)
        {
            pNode_ = NULL;
            pos_ = -1;
        }
    }

    iterator(const iterator& it)
        : pNode_(it.pNode_)
        , pos_(it.pos_)
    {
        if (!pNode_ || (int)pNode_->Size() <= pos_)
        {
            pNode_ = NULL;
            pos_ = -1;
        }
    }

    bool operator == (const iterator& it)
    {
        return pNode_ == it.pNode_ && pos_ == it.pos_;
    }

    bool operator != (const iterator& it)
    {
        return !(*this == it);
    }

    const ValueType& operator* ()
    {
        assert(pNode_);
        assert(pos_ >= 0 && pos_ < (int)pNode_->Size());

        return pNode_->GetNodeByIndex(pos_)->GetValue();
    }

    TreeNodePtr operator-> ()
    {
        assert(pNode_);
        assert(pos_ >= 0 && pos_ < (int)pNode_->Size());

        return pNode_->GetNodeByIndex(pos_);
    }

    iterator& operator++()
    {
        Advance();
        return *this;
    }

    iterator& operator++(int)
    {
        iterator old = *this;
        Advance();
        return old;
    }
    
private:
    void Advance()
    {
        if (!pNode_)
        {
            return;
        }

        ++pos_;

        if (pos_ < 0 || pos_ >= (int)pNode_->Size())
        {
            pNode_ = NULL;
            pos_ = -1;
            return;
        }
    }

    TreeNodePtr pNode_;
    int pos_;
    bool excludeSpecial_;
};

}//namespace acapella

#endif
